The invention relates to a method for processing a user program on a parallel computer system.
For processing on a parallel computer system, a user program can be divided into a plurality of processes which are processed concurrently on a plurality of processors of the parallel computer system. The situation may therefore arise that for execution a first process on one processor of the parallel computer system requires the result of a second process which is being processed on another processor of the parallel computer system, the result of which is not yet available. In this case, the two processes must be synchronized. One process must assume a wait state and wait for the termination of the other process. Once the result of the other process is available, then the first process can be continued (Interfaces in Computing, Vol. 3, Nos. 3/4, Sept.-Dec. '85, Lausanne CH, pp. 199-216, Elsevier Sequoia, NL).
An example of such program processing is the functional programming style in which a program consists of nested function calls. If a user program of this type runs on a parallel data processing system, the individual functions can run in different processes. A function supplies a result which can be transferred to another function as an argument and processed further there.
Depending on how they use their arguments, functions can be divided into two types:
Strict function
A function is strict if the function requires the values of individual arguments for execution. This is the case with arithmetic operations for example. An addition can only be executed if the values of all the arguments to be added are available.
Non-strict function
A function is non-strict if the values of all the arguments are not required for executing the function, that is to say the arguments are passed on to the function without the function looking at the value. Non-strict operations are assignment operations or PUSH operations for example.
As a result of the parallel processing of such functions, the situation may arise that a function requires as an argument the result of another function which is running in another process on another processor and is not yet terminated. In this case synchronization is necessary. In parallel data processing systems, the problem of the synchronization of functions can be solved as follows, depending on the type of function:
Case 1: A strict function requires as an argument the result of a function that is running concurrently with the strict function. PA1 Since the value of the strict argument is required by the function, in this case the functions must be synchronized, that is to say the strict function must wait for the computation of the argument. PA1 Case 2: A non-strict function has as an argument the result of a function that is running concurrently with the non-strict function. PA1 Since the non-strict function does not require the value of the argument, it is possible, for example, to introduce the concept of the placeholder for this purpose (Halstead, R: "Multilisp: A Language for Concurrent Symbolic Computation", ACM Transactions on Programming Languages and Systems, October 1985). It is possible to use these placeholders as if they were the result of the parallel process. The placeholder is used here instead of the argument for the execution of the non-strict function. Thus, for instance, a PUSH operation can be executed using a placeholder instead of the actual value. By means of this concept, the synchronization would be postponed until the time of the first strict use of the result. With the non-strict use of data it is consequently possible to dispense with synchronization and utilize better the parallel data processing system. PA1 The value of the argument is stored normally, so that it is possible to access the data directly. The strict operation can be executed. PA1 Instead of the argument there is a placeholder which points to the actual result. The result is in a result cell. If the result cell already contains the data, then it is possible to access this data with an additional memory access via the placeholder. The strict operation can then be executed. PA1 A placeholder, that is to say also a result cell, exists but it does not yet contain any result. The process which is to compute the result is still active. In this case synchronization must take place, that is to say the strict operation must wait for the termination of the process and the provision of the result in the result cell.
The concept of placeholders must be taken into account for the execution of strict operations. When a function is called, an argument may be available in three different states:
These three possible states of an argument require different handling. Modern functional language concepts for parallel processing, such as Multilisp for example, which permit a transparent processing of the results of processes free the program developer from the explicit handling of the different argument states. However, as a result the present state is static, that is to say as a rule cannot be decided at the time the user program is translated. The case distinction must therefore be performed at the user program runtime for each data access of a strict operation to its strict arguments.